//快速排序
//快速排序算法的基本思想是：
//   从数组中取出一个数，称之为基数（pivot）
//   遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
//   将左右两个区域视为两个数组，重复前两个步骤，直到排序完成

//时间复杂度为O(nlogn），最坏情况下为O(n2)。
//空间复杂度与递归层数有关，因为每层递归都会产生临时变量，因此为O(logn)~O(n)，平均空间复杂度为O(logn)

//是不稳定的排序

import java.util.Arrays;

public class quickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{6,2,1,4,8,7};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //快速排序入口
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    //方法重载

    //快速排序的框架：
    //终止条件、找中间值分区、对左右分区再进行快速排序
    //知道这个框架以后，主要考虑的就是怎样实现partition来找middle

    //这里partition采用的是双指针分区，其实只用一个指针进行搜索也可以，但并不那么好理解
    public static void quickSort(int[] arr, int start, int end) {
        // 如果区域内的数字少于 2 个，退出递归
        if (start >= end) return;
        // 将数组分区，并获得中间值的下标
        int middle = partition(arr, start, end);
        // 对左边区域快速排序
        quickSort(arr, start, middle - 1);
        // 对右边区域快速排序
        quickSort(arr, middle + 1, end);
    }

    // 将 arr 从 start 到 end 分区，左边区域比基数小，右边区域比基数大，然后返回中间值的下标
    public static int partition(int[] arr, int start, int end) {

        // 取第一个数为基数
        // 基数可以视为待分区数组的“轴”，在数组中轴的左边应该都比它小，右边应该都比它大，然后再对左右分区进行相同处理
        // “轴”最后的位置就是middle

        //基数可以任取，取第一个数比较容易理解
        int pivot = arr[start];

        // 从第二个数开始分区，左边界
        int left = start + 1;

        // 右边界
        int right = end;

        //双指针，从区域的头尾开始找需要交换位置的数，最后相遇则停止
        while (left < right) {
            // 找到第一个大于基数的位置
            while (left < right && arr[left] <= pivot) left++;
            // 找到第一个小于基数的位置
            while (left < right && arr[right] >= pivot) right--;
            // 交换这两个数，使得左边分区都小于或等于基数，右边分区大于或等于基数
            if (left < right) {
                exchange(arr, left, right);
                left++;
                right--;
            }
        }

        // 选取数组的第一个数为基数，在完成上面的分区步骤后，我们需要把基数和中间值进行交换，中间值会被分到左边区域，把基数放到它应该在的位置
        // 所以要保证，中间值的下标是分区完成后，最后一个比基数小的值

        // 值得注意的是，如果剩余的数组中只有最后一个数大于基数，当left == right时，其实并没有发生交换，right的位置是不对的，所以在最后要进行单独比较
        // 比如数组6,2,1,4,8,7就有这个问题，最后right和left会停在8
        // 如果 left 和 right 相等，单独比较 arr[right] 和 pivot
        // 如果arr[right]大于pivot，则此时right应当还要前移
        if (left == right && arr[right] > pivot) right--;

        // 将基数和轴交换，right指向的就是轴，即middle最后的位置
        exchange(arr, start, right);
        return right;
    }

    private static void exchange(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
